|
In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William,〔.〕 with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.〔.〕 The Moser spindle has also been called the Hajós graph after György Hajós, as it can be viewed as an instance of the Hajós construction.〔.〕 However, the name "Hajós graph" has also been applied to a different graph, in the form of a triangle inscribed within a hexagon.〔.〕 ==Construction== As a unit distance graph, the Moser spindle is formed by two rhombi with 60 and 120 degree angles, so that the sides and short diagonals of the rhombi form equilateral triangles. The two rhombi are placed in the plane, sharing one of their acute-angled vertices, in such a way that the remaining two acute-angled vertices are a unit distance apart from each other. The eleven edges of the graph are the eight rhombus sides, the two short diagonals of the rhombi, and the edge between the unit-distance pair of acute-angled vertices. The Moser spindle may also be constructed graph-theoretically, without reference to a geometric embedding, using the Hajós construction starting with two complete graphs on four vertices. This construction removes an edge from each complete graph, merges two of the endpoints of the removed edges into a single vertex shared by both cliques, and adds a new edge connecting the remaining two endpoints of the removed edge.〔 Another way of constructing the Moser spindle is as the complement graph of the graph formed from the utility graph ''K''3,3 by subdividing one of its edges.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Moser spindle」の詳細全文を読む スポンサード リンク
|